package com.tgy.algorithm._经典题目01;

/**
 * 给定一个二叉树的头节点head，路径的规定有以下三种不同的规定
 * 1)路径必须是头节点出发，到叶节点为止，返回最大路径和
 * 2)路径可以从任何节点出发，但必须往下走到达任何节点，返回最大路径和
 * 3)路径可以从任何节点出发，到任何节点，返回最大路径和
 */

import com.tgy.algorithm.base.other.BiTreeNode;

public class _007_二叉树路径和问题 {

    public static BiTreeNode generalBiTreeNode() {

        /**
         *               4
         *           2        3
         *       -2     -4 -2     -1
         */

        BiTreeNode root = new BiTreeNode(4);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(-2);
        root.left.right = new BiTreeNode(-4);
        root.right.left = new BiTreeNode(-2);
        root.right.right = new BiTreeNode(-1);
        return root;
    }

    public static int maxPathValue = Integer.MIN_VALUE;

    public static int rootToLeaf01(BiTreeNode root) {

        doRootToLeaf01(root,0);
        return maxPathValue;
    }

    public static void doRootToLeaf01(BiTreeNode root,int pathValue) {

        if (root.left == null && root.right == null) {
            maxPathValue = Math.max(maxPathValue,pathValue + root.value);
            return;
        }

        if (root.left != null) {
            doRootToLeaf01(root.left,pathValue + root.value);
        }

        if (root.right != null) {
            doRootToLeaf01(root.right,pathValue+root.value);
        }
    }

    public static int rootToLeaf02(BiTreeNode root) {
        return doRootToLeaf02(root);
    }

    public static int doRootToLeaf02(BiTreeNode root) {

        if (root.left == null && root.right == null) {
            return root.value;
        }

        int leftVal = Integer.MIN_VALUE;
        if (root.left != null) {
            leftVal = doRootToLeaf02(root.left);
        }

        int rightVal = Integer.MIN_VALUE;
        if (root.right != null) {
           rightVal = doRootToLeaf02(root.right);
        }

        return Math.max(leftVal+root.value,rightVal+root.value);
    }

    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
//        int val = rootToLeaf01(root);
        int val = rootToLeaf02(root);
        System.out.println(val);
    }
}
